/**
 * Exercise 3.26
 * ----------------------------------------------------------------------
 * Write a code fragment that,
 * given pointers `x` and `t` to two disjoint circular lists,
 * inserts the list pointed to by `t` into the list pointed to by `x`,
 * at the point following `x`.
 * -----------------------------------------------------------------------
 * 
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int Item;
typedef struct node *link;

struct node {
    Item item;
    link next;
};

void insert(link x, link t);
void test_single_node_insert();
void test_multi_node_insert();
void test_insert_at_end();

int main(int argc, char **argv) {
    test_single_node_insert();
    test_multi_node_insert();
    test_insert_at_end();
    return 0;
}

void insert(link x, link t){
    assert(x != NULL);
    assert(t != NULL);
    link xNext = x->next;
    // 先找到指向t的前一个节点
    link tLast = t;
    while (tLast->next != t) {
        tLast = tLast->next;
    }
    x->next = t;
    tLast->next = xNext;
}

void test_single_node_insert() {
    link x = malloc(sizeof(struct node));
    x->next = x; // x 自环
    link t = malloc(sizeof(struct node));
    t->next = t; // t 自环
    
    insert(x, t);
    
    assert(x->next == t);
    assert(t->next == x); // 新链表应为 x→t→x
    
    free(x);
    free(t);
}

void test_multi_node_insert() {
    // 构建 x 链表: A → B → x → C → A
    link A = malloc(sizeof(struct node));
    link B = malloc(sizeof(struct node));
    link x = malloc(sizeof(struct node));
    link C = malloc(sizeof(struct node));
    A->next = B;
    B->next = x;
    x->next = C;
    C->next = A;
    
    // 构建 t 链表: t → D → E → t
    link t = malloc(sizeof(struct node));
    link D = malloc(sizeof(struct node));
    link E = malloc(sizeof(struct node));
    t->next = D;
    D->next = E;
    E->next = t;
    
    insert(x, t);
    
    // 验证插入后的连接
    assert(x->next == t);       // x → t
    assert(E->next == C);       // E → C
    assert(C->next == A);       // 保持原循环
    
    // 释放内存
    free(A); free(B); free(x); free(C);
    free(t); free(D); free(E);
}

void test_insert_at_end() {
    // 构建 x 链表: A → x → B → A
    link A = malloc(sizeof(struct node));
    link x = malloc(sizeof(struct node));
    link B = malloc(sizeof(struct node));
    A->next = x;
    x->next = B;
    B->next = A;
    
    // 构建 t 链表: t → C → t
    link t = malloc(sizeof(struct node));
    link C = malloc(sizeof(struct node));
    t->next = C;
    C->next = t;
    
    insert(B, t); // 在 B 后插入 t 链表
    
    assert(B->next == t);  // B → t
    assert(C->next == A);  // C → A
    assert(A->next == x);  // 原结构不变
    
    free(A); free(x); free(B);
    free(t); free(C);
}